package com.ycz.algorithm.utils.tree.avl;

import sun.reflect.generics.tree.Tree;

/**
 * @author yancz
 * @ClassName AVLTreeValidatoar
 * @description: AVL树工具类，判定一颗树是否为AVL树
 * @date 2024-12-23 16:26:09
 * @version: 1.0
 */
public class AVLTreeValidatoar {

    static class Result {  // 辅助类，递归判断
        boolean isAVL;  // 表示当前节点的子树是否为一个AVL树
        int height; // 当前子树的高度

        Result(boolean isAVL, int height) {
            this.isAVL = isAVL;
            this.height = height;
        }

    }

    public boolean isAVLTree(TreeNode root) {
        return checkAVL(root).isAVL;
    }

    /*
     * @author yancz
     * @description 判断树是否为平衡二叉搜索树，需满足以下两个条件：
     * 条件一：对于每棵树及其子树，均满足左子树值 < 根节点值 < 右子树值
     * 条件二：对于每个节点，其左子树高度与右子树高度之差的绝对值不超过1，即差值属于1,0,-1中的一个
     * @date 2024/12/23 16:28
     * @param root 根结点
     * @return Result
     **/
    private Result checkAVL(TreeNode root) {
        if (root == null) {
            return new Result(true, -1); // 空树的子树高度为-1
        }
        // 检查左子树
        Result leftResult = checkAVL(root.left);
        // 检查右子树
        Result rightResult = checkAVL(root.right);
        if (!leftResult.isAVL || !rightResult.isAVL) { // 如果左子树或右子树不是AVL树，那么该树不是AVL树
            return new Result(false, 0);
        }
        // 计算平衡因子
        int balanceFactor = Math.abs(leftResult.height - rightResult.height);
        if (balanceFactor > 1) { // 平衡因子绝对值大于1，则不是AVL树
            return new Result(false, 0);
        }
        // 若左子节点的值>=当前节点值，不是BST树，则不是AVL树
        if (root.left != null && root.left.val >= root.val) {
            return new Result(false, 0);
        }
        // 若右子节点的值<=当前节点值，不是BST树，则不是AVL树
        if (root.right != null && root.right.val <= root.val) {
            return new Result(false, 0);
        }
        // 计算当前左右子树的最大高度
        int currentHeight = Math.max(leftResult.height, rightResult.height) + 1;
        return new Result(true, currentHeight);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(5);
        root.left = left;
        root.right = right;
        AVLTreeValidatoar avlTreeValidatoar = new AVLTreeValidatoar();
        boolean isAVL = avlTreeValidatoar.isAVLTree(root);
        System.out.println("是否为AVL树：" + isAVL);
        TreeNode left_1 = new TreeNode(2);
        left.left = left_1;
        System.out.println("是否为AVL树：" + avlTreeValidatoar.isAVLTree(root));
        TreeNode right_1 = new TreeNode(6);
        right.right = right_1;
        System.out.println("是否为AVL树：" + avlTreeValidatoar.isAVLTree(root));
        TreeNode left_2 = new TreeNode(1);
        left_1.left = left_2;
        System.out.println("是否为AVL树：" + avlTreeValidatoar.isAVLTree(root));
        TreeNode left_1_right = new TreeNode(4);
        left.right = left_1_right;
        System.out.println("是否为AVL树：" + avlTreeValidatoar.isAVLTree(root));
    }

}
